package ink.lovejinhu.leetcodeMatch;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author jinhu
 * created 2021-08-08 10:39
 */
public class Solution_5839 {


    public int minStoneSum2(int[] piles, int k) {
        //大根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(((o1, o2) -> o2 - o1));
        for (int i = 0; i < piles.length; i++) {
            priorityQueue.offer(piles[i]);
        }
        while (k > 0 && !priorityQueue.isEmpty()) {
            // 当前数组最大值
            int pop = priorityQueue.poll();
            // 最大值减去自身的一半放入大根堆
            int temp = pop - (pop >> 1);
            priorityQueue.add(temp);
            k--;
        }
        int res = 0;
        while (!priorityQueue.isEmpty()) {
            res += priorityQueue.poll();
        }

        return res;
    }

    public int minStoneSum(int[] piles, int k) {
        for (int i = 0; i < k; i++) {
            int maxValueIndex = this.findMaxValueIndex(piles);
            if (piles[i] == 1) {
                break;
            }
            piles[maxValueIndex] = piles[maxValueIndex] - piles[maxValueIndex] / 2;
        }
        int res = 0;
        for (int i = 0; i < piles.length; i++) {
            res += piles[i];
        }
        return res;
    }

    public int findMaxValueIndex(int[] piles) {
        int index = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < piles.length; i++) {
            if (piles[i] > max) {
                max = piles[i];
                index = i;
            }
        }
        return index;
    }

    public int minStoneSum1(int[] piles, int k) {
        Arrays.sort(piles);
        if (k <= piles.length) {
            int res = 0;
            int j = piles.length - 1;
            for (int i = k; i >= 1; i--) {
                piles[j] = piles[j] - piles[j] / 2;
                res += piles[j];
                j--;
            }
            for (int i = j; i >= 0; i--) {
                res += piles[i];
            }
            return res;
        } else {   //k>piles.length
            int i = k / piles.length;
            int j = k % piles.length;
            int res = 0;
            int t = 0;
            if (j == 0) {
                t = i;
            } else {
                t = i + 1;
            }

            for (int l = piles.length - 1; l >= piles.length - j; l--) {
                int z = t;
                while (z > 0) {
                    piles[l] = piles[l] - piles[l] / 2;
                    if (piles[l] == 1) {
                        break;
                    }
                    z--;
                }
            }
            for (int l = piles.length - j - 1; l >= 0; l--) {
                int z = i;
                while (z > 0) {
                    piles[l] = piles[l] - piles[l] / 2;
                    if (piles[l] == 1) {
                        break;
                    }
                    z--;
                }
            }
            for (int l = 0; l < piles.length; l++) {
                res += piles[l];
            }
            return res;
        }

    }

    public static void main(String[] args) {
        Solution_5839 solution_5839 = new Solution_5839();
        int[] piles = {1391, 5916};
        int k = 3;
        int i = solution_5839.minStoneSum1(piles, k);
        System.out.println(i);
    }
}
